package william.backtracing;

/**
 * @author ZhangShenao
 * @date 2024/4/6
 * @description <a href="https://leetcode.cn/problems/word-search/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode79_单词搜索 {
    /**
     * 标记每个位置的字母是否被访问过
     */
    private boolean[][] visited;

    /**
     * 移动方向数组
     */
    private int[][] move = new int[4][2];

    /**
     * 搜索范围
     */
    private int X;
    private int Y;


    /**
     * 使用递归+回溯算法实现
     */
    public boolean exist(char[][] board, String word) {
        //边界条件校验
        if (board == null || board.length < 1) {
            return false;
        }

        //初始化
        X = board.length;
        Y = board[0].length;
        visited = new boolean[X][Y];
        move[0] = new int[]{0, 1};
        move[1] = new int[]{0, -1};
        move[2] = new int[]{-1, 0};
        move[3] = new int[]{1, 0};

        //遍历二维数组,依次以每个元素为起点,判断是否可以搜索到单词
        for (int i = 0; i < X; i++) {
            for (int j = 0; j < Y; j++) {
                if (find(board, word, 0, i, j)) {
                    return true;    //找到直接返回true
                }
            }
        }

        //未找到,返回false
        return false;
    }

    /**
     * 递归+回溯实现
     * 以board[x][y]元素为起点,寻找单词word的第index个字母,返回是否找到
     */
    private boolean find(char[][] board, String word, int idx, int x, int y) {
        //递归终止条件
        if (idx == word.length() - 1) { //仅剩一个字母,判断该字母是否与当前位置的字母相等
            return (word.charAt(idx) == board[x][y]);
        }

        if (word.charAt(idx) != board[x][y]) {   //当前位置的字母不匹配,直接返回false
            return false;
        }

        visited[x][y] = true;   //访问记录

        //当前字母匹配,继续向上、下、左、右四个方向寻找
        boolean found = false;
        for (int i = 0; i < 4; i++) {
            int newX = x + move[i][0];
            int newY = y + move[i][1];
            if (isValidPos(newX, newY) && !visited[newX][newY]) {
                found = find(board, word, idx + 1, newX, newY);
                if (found) {
                    break;
                }
            }
        }

        //回溯:当前位置已经寻找完成,将当前位置从访问记录中移除
        visited[x][y] = false;

        return found;
    }

    /**
     * 判断坐标是否在有效范围内
     */
    private boolean isValidPos(int x, int y) {
        return (x >= 0 && x < X && y >= 0 && y < Y);
    }
}
